package com.mango.leet.code.week1.game388;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: mango
 * @Date: 2024/3/10 12:39
 */
public class LC100247 {
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    LinkedList<Integer> track = new LinkedList<>();
    // track 中的元素会被标记为 true
    boolean[] used;
    long result = 0;

    public long maximumHappinessSum(int[] happiness, int k) {
        used = new boolean[happiness.length];
        backtrack(happiness, k);
        return result;
    }

    // 回溯算法核心函数
    void backtrack(int[] nums, int k) {
        // base case，到达叶子节点
        if (track.size() == k) {
            // 收集叶子节点上的值
            res.add(new LinkedList(track));
            result = Math.max(result, sum(track));
            return;
        }

        // 回溯算法标准框架
        for (int i = 0; i < nums.length; i++) {
            // 已经存在 track 中的元素，不能重复选择
            if (used[i]) {
                continue;
            }
            // 做选择
            used[i] = true;
            add(nums, -1, i);
            track.addLast(nums[i]);
            // 进入下一层回溯树
            backtrack(nums, k);
            // 取消选择
            track.removeLast();
            used[i] = false;
            add(nums, 1, i);
        }
    }
    private long sum(LinkedList<Integer> list) {
        long sum = 0;
        for (int i = 0; i < list.size(); i++) {
            sum += list.get(i);
        }
        return sum;
    }
    private void add(int[] nums, int value, int index) {
        for (int i = 0; i < nums.length; i++) {
            if (i == index) {
                continue;
            }
            nums[i] += value;
            if (nums[i] < 0) {
                nums[i] = 0;
            }
        }
    }
    public static void main(String[] args) {
        int[] happiness = {1,1,1,1};
        int k = 2;
        LC100247 t = new LC100247();
        long result = t.maximumHappinessSum(happiness, k);
        System.out.println(result);
    }
}
